package com.yanceysong.codetop.s51_s60;


public class S52_Easy_70_爬楼梯 {
    /**
     * . LeetCode 70. 爬楼梯 (Climbing Stairs)
     * .<p>
     * .题目链接：<a href="https://leetcode.cn/problems/climbing-stairs/">https://leetcode.cn/problems/climbing-stairs/</a>
     * .<p>
     * .【题目描述】
     * .你正在爬楼梯。需要到达顶部一共需要 n 阶台阶。每次你可以爬 1 阶或者 2 阶。
     * .问：你有多少种不同的方法可以爬到楼顶？
     * .<p>
     * .【示例】
     * .示例1：n = 2 -> 2（方式：1+1、2）
     * .示例2：n = 3 -> 3（方式：1+1+1、1+2、2+1）
     * .示例3：n = 5 -> 8
     * .<p>
     * .【标签】动态规划 / 斐波那契 / 记忆化 / 数学
     * .<p>
     * .【核心思路】
     * .到达第 n 阶的方法数 = 到达第 n-1 阶后再迈 1 阶 + 到达第 n-2 阶后再迈 2 阶。
     * .定义 ways[i] 表示到达第 i 阶的不同方法数：
     * .递推：ways[i] = ways[i-1] + ways[i-2]
     * .初始：ways[0] = 1 (作为“站在地面”基准)、ways[1] = 1
     * .所以与经典 Fibonacci 序列一致（只是起始项语义稍有不同）。
     * .<p>
     * .【ASCII 递推图】（以 n=5 为例）
     * .  ways[0] = 1
     * .  ways[1] = 1
     * .  ways[2] = ways[1] + ways[0] = 2
     * .  ways[3] = ways[2] + ways[1] = 3
     * .  ways[4] = ways[3] + ways[2] = 5
     * .  ways[5] = ways[4] + ways[3] = 8
     * .        ┌─────────────┐
     * .  i:    0   1   2   3   4   5
     * .  ways: 1   1   2   3   5   8
     * .<p>
     * .【关键洞察】
     * .1. 只与前两项有关 -> 可以将 O(n) 空间优化到 O(1)。
     * .2. 该问题本质是 Fibonacci 的平移版本；很多题（跳台阶、爬楼梯、打家劫舍的局部递推）都有类似“前两状态组合”。
     * .3. ways[0] = 1 作为“起点”很关键，代表尚未开始爬时有 1 种方式（即不动），方便统一公式。
     * .4. n 最大为 45（LeetCode 约束） -> int 类型不会溢出，因为 Fibonacci(45)=1,836,311,903 < 2^31-1。
     * .<p>
     * .【复杂度分析】
     * .- DP 数组写法：时间 O(n)，空间 O(n)
     * .- 优化迭代写法：时间 O(n)，空间 O(1)
     * .- 数学公式（Binet）不推荐：会有浮点误差。
     * .<p>
     * .【常见易错点】
     * .- 忘记处理 n=1 的边界。
     * .- ways[0] 设为 0 导致错位。
     * .- 使用数组但没有进行空间优化（可以根据需要保留数组以便教学演示）。
     */
    public int climbStairs(int stairsTotal) {
        // 边界情况：n 为 0 或 1，直接返回 1
        if (stairsTotal <= 1) {
            return 1; // n=0 视作在地面，有 1 种“完成”方式；n=1 只能爬 1 阶
        }
        // ways[i] 表示到达第 i 阶的不同方法数
        int[] ways = new int[stairsTotal + 1];
        ways[0] = 1; // 基准：站在 0 阶（地面）只有 1 种方式
        ways[1] = 1; // 直接迈到第 1 阶只有 1 种方式
        for (int step = 2; step <= stairsTotal; step++) {
            // 当前阶方法数 = 上一阶方法数(再迈 1 阶) + 上两阶方法数(再迈 2 阶)
            ways[step] = ways[step - 1] + ways[step - 2];
        }
        return ways[stairsTotal];
    }

    /**
     * .空间优化版本：只保留最近两个状态，滚动更新。
     * .@param stairsTotal 台阶数 n
     * .@return 不同爬法数量
     */
    public int climbStairsOptimized(int stairsTotal) {
        if (stairsTotal <= 1) return 1;
        int prev = 1;     // ways[i-2]
        int curr = 1;     // ways[i-1]
        for (int step = 2; step <= stairsTotal; step++) {
            int next = prev + curr; // ways[i]
            prev = curr;
            curr = next;
        }
        return curr;
    }

    /**
     * .递归 + 记忆化（演示用，不推荐大规模调用）
     */
    public int climbStairsMemo(int n) {
        int[] memo = new int[n + 1];
        return dfs(n, memo);
    }

    private int dfs(int k, int[] memo) {
        if (k <= 1) return 1;
        if (memo[k] != 0) return memo[k];
        memo[k] = dfs(k - 1, memo) + dfs(k - 2, memo);
        return memo[k];
    }

    // ===================== 测试方法 =====================

    private static void runCase(int n, int expected) {
        S52_Easy_70_爬楼梯 solver = new S52_Easy_70_爬楼梯();
        int dpResult = solver.climbStairs(n);
        int optResult = solver.climbStairsOptimized(n);
        int memoResult = solver.climbStairsMemo(n);
        boolean pass = dpResult == expected && optResult == expected && memoResult == expected;
        System.out.printf("n=%d | dp=%d opt=%d memo=%d | expected=%d | %s\n", n, dpResult, optResult, memoResult, expected, pass ? "PASS" : "FAIL");
        assert pass : "测试失败 n=" + n;
    }

    /**
     * .主方法：运行多个测试用例。
     */
    public static void main(String[] args) {
        System.out.println("=== 爬楼梯题目测试开始 ===");

        // 基础边界
        runCase(0, 1); // 定义：地面 1 种方式
        runCase(1, 1);
        runCase(2, 2); // (1+1,2)
        runCase(3, 3); // (1+1+1,1+2,2+1)
        runCase(4, 5);
        runCase(5, 8);

        // 中等规模
        runCase(10, 89); // Fibonacci(10) with base = 89
        runCase(15, 987);
        runCase(20, 10946);

        // 上界附近 (LeetCode n <= 45)
        runCase(30, 1346269);
        runCase(35, 14930352);
        runCase(45, 1836311903);

        System.out.println("=== 所有测试完成 ===");
        System.out.println("(提示：若需断言生效，请使用 -ea 运行 JVM)");
    }
}
